package com.ma.tree;

import java.util.Objects;
import java.util.Queue;
import java.util.Set;

class Node {

    public Node[] neibor;

}

//BFS计算从起点start到终点end的最短距离
public class BFSCode {
    int BFS(Node start, Node end) {
        //核心数据结构
        Queue<Node> q = null;
        //避免走回头路
        Set<Node> visited = null;
        q.offer(start);
        visited.add(start);

        //记录扩散的步数
        int step = 0;
        while (!q.isEmpty()) {
            //将当前队列中的所有节点向四周扩散
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                Node cur = q.poll();
                //!!这里判断是否到达终点
                if (Objects.equals(cur, end)) {
                    return step;
                }
                //将 cur 的相邻节点加入队列
                for (Node x : cur.neibor) {
                    if (!visited.contains(x)) {
                        q.offer(x);
                        visited.add(x);
                    }
                }
            }
        }
        step++;
        return step;
    }
}
